﻿#define _CRT_SECURE_NO_WARNINGS 1
#include"BinaryTree.h"
BTNode* BuyNode(BTDatatype x)
{
	BTNode* node= (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc");
		return NULL;
	}
	node->data = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}
BTNode* CreatBinaryTree()//创建二叉树
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);
	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	return node1;
}
void PreOrder(BTNode* root)//前序
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);

}
void InOrder(BTNode* root)//中序
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}
void PostOrder(BTNode* root)//后序
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}
int BinaryTreeSize(BTNode* root)//节点个数
{
	if (root == NULL)
	{
		return 0;
	}
	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
int BinaryTreeleafSize(BTNode* root)//叶子结点个数
{
	if (root == NULL)
	{
		return 0;
	}

	if ((root->left)==NULL && (root->right) == NULL)
		return 1;
	
	return BinaryTreeleafSize(root->left) + BinaryTreeleafSize(root->right);

}
int BinaryTreeHeight(BTNode* root)//求树的高度
{
	if (root == NULL)
	{
		return 0;
	}
	int h1 = BinaryTreeHeight(root->left);
	int h2 = BinaryTreeHeight(root->right);
	return h1 > h2 ? h1+1 : h2+1;
}
int BinaryTreeleafkSize(BTNode* root,int k)//第K层叶子节点的个数;
{
	assert(k > 0);
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeleafkSize(root->left,k-1) + BinaryTreeleafkSize(root->right,k-1);
}
BTNode* BinaryTreeFind(BTNode* root, BTDatatype x)//查找值为x的结点
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
	{
		return root;
	}
	BTNode* ret1 = BinaryTreeFind(root->left, x);
	if (ret1)
	{
		return ret1;
	}
	BTNode* ret2 = BinaryTreeFind(root->right, x);
	if (ret2)
	{
		return ret2;
	}
	return NULL;
	
}
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if(root)
	QueuePush(&q, root);
	int levelSize = 1;
	while (!QueueEmpty(&q))
	{
		while (levelSize--)
		{
			BTNode* top = QueueFront(&q);
			QueuePop(&q);
			printf("%d ", top->data);
			if (top->left)
			{
				QueuePush(&q, top->left);
			}
			if (top->right)
			{
				QueuePush(&q, top->right);
			}
			

		}
		printf("\n");
		levelSize = QueueSize(&q);
	}
	QueueDestroy(&q);
}
void BinaryTreeDestroy(BTNode* root)//二叉树的销毁
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreeDestroy(root->left);
	BinaryTreeDestroy(root->right);
	free(root);
}
bool BinaryTreeComplete(BTNode* root)//判断是否为完全二叉树
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q,root);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		if (top == NULL)
		{
			break;
		}
		QueuePush(&q, top->left);
		QueuePush(&q, top->right);

		}
	while (!QueueEmpty(&q))
	{

		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		if (top)
		{
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}